package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import java.util.HashMap;
import java.util.Map;

/**
 * 一种消息接收并打印的结构设计
 * 已知一个消息流会不断地吐出整数 1~N，但不一定按照顺序吐出。
 * 如果上次打印的数为 i， 那么当 i+1 出现时，请打印 i+1 及其之后接收过的并且连续的所有数，
 * 直到 1~N 全部接收 并打印完，请设计这种接收并打印的结构。
 * 初始时默认i==0
 *
 * 0号包到n号包一定会给，但是顺序不一定。要求，顺序输出。
 * @author: caoyanan
 * @time: 2021/5/24 7:13 下午
 */
public class Question03_OrderedPlay {

    public static void main(String[] args) {

        MessageBox box = new MessageBox();

        box.receive(2,"B"); // - 2"
        box.receive(1,"A"); // 1 2 -> print, trigger is 1

        box.receive(4,"D"); // - 4
        box.receive(5,"E"); // - 4 5
        box.receive(7,"G"); // - 4 5 - 7
        box.receive(8,"H"); // - 4 5 - 7 8
        box.receive(6,"F"); // - 4 5 6 7 8
        box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3

        box.receive(9,"I"); // 9 -> print, trigger is 9

        box.receive(10,"J"); // 10 -> print, trigger is 10

        box.receive(12,"L"); // - 12
        box.receive(13,"M"); // - 12 13
        box.receive(11,"K"); // 11 12 13 -> print, trigger is 11


    }

    public static class MessageBox {

        private Map<Integer, Node> headMap;
        private Map<Integer, Node> tailMap;
        private Integer next;

        public MessageBox() {
            headMap = new HashMap<>();
            tailMap = new HashMap<>();
            next = 1;
        }


        public void receive(int index, String info) {

            //收到一条消息首先分别放到头节点上
            Node node = new Node(info);
            headMap.put(index, node);
            tailMap.put(index, node);

            //有可能该节点是一个新的尾部，所以在尾部表里面查一查是否有它的上一个节点
            if (tailMap.containsKey(index - 1)) {
                Node pre = tailMap.get(index - 1);
                pre.next = node;
                tailMap.remove(index-1);
            }
            //其次，有可能这个节点是一个新的头部，所以在头部表找一下该节点的下一个节点
            if (headMap.containsKey(index + 1)) {
                node.next = headMap.get(index + 1);
                headMap.remove(index + 1);
            }

            print(index);
        }

        private void print(int index) {
            if (index != next) {
                return;
            }
            Node node = headMap.get(index);
            headMap.remove(index);
            while (node != null) {
                System.out.print(node.info + " ");
                next++;
                node = node.next;
            }
            System.out.println();
        }
    }

    public static class Node {

        private Node next;
        private final String info;

        public Node(String info) {
            this.info = info;
        }
    }
}
